#include<bits/stdc++.h>
using namespace std;
int n,t;
string f1,f2,tmp,s;
bool ok(int x)
{
	if(s.size()+x>f2.size()) return 0;
	for(int i = 0;i<s.size();i++)
		if(s[i]!=f2[x+i])
			return 0;
	return 1;
}
signed main()
{
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>t;
	if(n<=10&&t<=10)
	{
		f1 = "0",f2 = "1";
		for(int i = 3;i<=n;i++)
			tmp = f2,f2 = f2+f1,f1 = tmp;
		while(t--)
		{
			cin>>s;
			int ans = 0;
			for(int i = 0;i<f2.size();i++)
				if(ok(i))
					ans++;
			cout<<ans<<'\n';
		}
	}
	return 0;
}

